package com.example.recursion;

import java.util.ArrayList;
import java.util.List;

/**
 * @Date 2022/7/7
 * @Created by Jonathan
 */
public class PrintAllPermutation {
    public static void main(String[] args) {
        final List<String> list = getList("abc");
        System.out.println(list);
    }


    private static List<String> getList(String str) {
        final char[] chars = str.toCharArray();
        List<String> ans = new ArrayList<>();
        process(0, chars, ans);
        return ans;
    }

    /**
     * str[0..i-1]已经做好决定了的
     * i及其以后的字符都有可能来到i位置
     * str[i..]都有机会来到i位置
     * i终止位置，str当前的样子，就是一种结果 -> ans
     */
    public static void process(int i, char[] str, List<String> ans) {
        if (i == str.length) {
            ans.add(String.valueOf(str));
            return;
        }
        // 妙啊
        // i后面所有的位置都有机会
        for (int j = i; j < str.length; j++) {
            swap(str, i, j);
            process(i + 1, str, ans);
            // 恢复现场
            swap(str, j, i);
        }
    }


    public static void process2(int i, char[] str, List<String> ans) {
        if (i == str.length) {
            ans.add(String.valueOf(str));
            return;
        }
        // 妙啊
        // i后面所有的位置都有机会
        boolean[] visited = new boolean[26];
        for (int j = i; j < str.length; j++) {
            // 分支限界  去重
            // str[j] = 'z' -> 25 visit[25] -> 'z'
            if (!visited[str[j] - 'a']) {
                visited[str[j] - 'a'] = true;
                swap(str, i, j);
                process2(i + 1, str, ans);
                // 恢复现场
                swap(str, j, i);
            }
        }
    }

    private static void swap(char[] str, int i, int j) {
        char temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }

}
